package com.lw.leetcode.arr.b;

import java.util.PriorityQueue;

/**
 * Created with IntelliJ IDEA.
 * 6231. 雇佣 K 位工人的总代价
 *
 * @author liw
 * @version 1.0
 * @date 2022/11/7 9:13
 */
public class TotalCost {

    public static void main(String[] args) {
        TotalCost test = new TotalCost();

        // 11
//        int[] arr = {17, 12, 10, 2, 7, 2, 11, 20, 8};
//        int k = 3;
//        int candidates = 4;

        // 4
        int[] arr = {1, 2, 4, 1};
        int k = 3;
        int candidates = 3;

        long l = test.totalCost(arr, k, candidates);
        System.out.println(l);

    }

    public long totalCost(int[] costs, int k, int candidates) {
        int st = candidates;
        int end = costs.length - 1 - candidates;
        PriorityQueue<Integer> as = new PriorityQueue<>();
        PriorityQueue<Integer> bs = new PriorityQueue<>();
        for (int i = 0; i < candidates; i++) {
            as.add(costs[i]);
        }
        int limit = Math.max(costs.length - candidates, candidates);
        for (int i = limit; i < costs.length; i++) {
            bs.add(costs[i]);
        }
        long sum = 0;
        while (k > 0) {
            if (as.isEmpty()) {
                sum += bs.poll();
                if (end >= st) {
                    bs.add(costs[end--]);
                }
            } else if (bs.isEmpty()) {
                sum += as.poll();
                if (end >= st) {
                    as.add(costs[st++]);
                }
            } else {
                Integer b = bs.peek();
                Integer a = as.peek();
                if (a <= b) {
                    sum += as.poll();
                    if (end >= st) {
                        as.add(costs[st++]);
                    }
                } else {
                    sum += bs.poll();
                    if (end >= st) {
                        bs.add(costs[end--]);
                    }
                }
            }
            k--;
        }
        return sum;
    }

}
